#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int longestPalindrome(string s) {
        int arr[128] = { 0 };
        for (auto e : s)
        {
            arr[e]++;
        }
        int ret = 0;
        for (int i = 0; i < 128; i++)
        {
            ret += arr[i] / 2 * 2;
        }
        if (ret < s.size())
            ret++;
        return ret;
    }
};

class Solution {
public:
    vector<int> diStringMatch(string s) {
        vector<int> ret;
        int left = 0;
        int right = s.size();
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == 'I')
            {
                ret.push_back(left++);
            }
            else
            {
                ret.push_back(right--);
            }
        }
        ret.push_back(left);
        return ret;
    }
};

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int size1 = s.size();
        int size2 = g.size();

        int left = 0;
        int ret = 0;
        if (size1 >= size2)
        {
            for (int i = size1 - size2; i < size1; i++)
            {
                if (s[i] >= g[left])
                {
                    left++;
                    ret++;
                }
            }
        }
        else
        {
            for (int i = 0; i < size1; i++)
            {
                if (s[i] >= g[left])
                {
                    left++;
                    ret++;
                }
            }
        }

        return ret;
    }
};

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        if (nums.size() == 1)
            return to_string(nums[0]);
        else if (nums.size() == 2)
            return to_string(nums[0]) + '/' + to_string(nums[1]);
        string ret;
        ret += to_string(nums[0]);
        for (int i = 1; i < nums.size(); i++)
        {
            ret += '/';
            if (i == 1)
            {
                ret += '(';
            }
            ret += to_string(nums[i]);
            if (i == nums.size() - 1)
                ret += ')';
        }
        return ret;
    }
};


class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (nums.size() == 1)
            return 0;
        int step = 0;
        int next1 = 0;
        int next2 = 0;
        for (int i = 0; i < nums.size(); i++)
        {

            if (i <= next1)
            {
                if (i + nums[i] >= n - 1)
                    return ++step;
                else if (i + nums[i] > next2)
                {
                    next2 = i + nums[i];
                }
            }
            if (i == next1)
            {
                step++;
                next1 = next2;
            }

        }
        return 0;
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int end = 0;
        int maxpos = 0;
        if (nums.size() == 1)
            return true;
        for (int i = 0; i < nums.size(); i++)
        {
            int tmp = i + nums[i];
            if (tmp >= nums.size() - 1)
                return true;
            maxpos = max(maxpos, i + nums[i]);
            //if(maxpos>=nums.size()-1)
                //return true;
            if (i == end)
            {
                if (end == maxpos)
                    return false;
                end = maxpos;
            }
        }
        return true;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int size = gas.size();
        for (int i = 0; i < gas.size(); i++)
        {
            if (gas[i] >= cost[i])
            {
                int j = i + 1;
                j %= size;
                int surplus = gas[i] - cost[i];
                while (j != i)
                {
                    surplus += gas[j] - cost[j];
                    if (surplus >= 0)
                    {
                        j++;
                        j %= size;
                    }
                    else
                    {
                        break;
                    }
                }
                if (j == i)
                    return i;
                if (j > i)
                    i = j;
                else
                    return -1;
            }
        }
        return -1;
    }
};